package com.zhouxianglh.p4;

import java.util.ArrayList;
import java.util.List;

/**
 * 4. 寻找两个有序数组的中位数
 * <p>
 * 这里不需要完全合并,只需要计算出中位数的位置,合并到位置之后,直接输出就可以了
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays2(new int[]{}, new int[]{2, 3}));
        System.out.println(findMedianSortedArrays2(new int[]{1, 3}, new int[]{2}));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        for (int i : nums1) {
            list.add(i);
        }
        for (int i : nums2) {
            list.add(i);
        }
        list.sort(Integer::compareTo);
        if (list.size() % 2 == 0) {
            int index = list.size() >> 1;
            return (list.get(index) + list.get(index - 1)) / 2.0;
        } else {
            return list.get(list.size() >> 1);
        }
    }

    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>(nums1.length + nums2.length);
        int index1 = 0;
        int index2 = 0;
        while (true) {
            if (index1 >= nums1.length) {
                if (index2 >= nums2.length) {
                    break;
                }
                list.add(nums2[index2++]);
            } else if (index2 >= nums2.length) {
                if (index1 >= nums1.length) {
                    break;
                }
                list.add(nums1[index1++]);
            } else {
                int a = nums1[index1];
                int b = nums2[index2];
                if (a > b) {
                    list.add(b);
                    index2++;
                } else {
                    list.add(a);
                    index1++;
                }
            }
        }
        if (list.size() % 2 == 0) {
            int index = list.size() >> 1;
            return (list.get(index) + list.get(index - 1)) / 2.0;
        } else {
            return list.get(list.size() >> 1);
        }
    }
}
